package com.leetcode.q4;

/**
 * <p> description: desc</p>
 *
 * @author tanzc
 * @date 2022/3/29
 **/
public class FindMedianSortedArrays {
    // 将两数组最小的数加到新数组里面，直到新数组长度超过中位数位置
    // 也就是不用全部合并
    // 时间复杂度O(m + n)
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length = nums1.length + nums2.length;
        int[] nums3 = new int[length];
        int loc = length / 2 + 1;
        int x = 0, y = 0, z = 0, s3 = 0;
        while(x < nums1.length && y < nums2.length && z < loc) {
            if(nums1[x] <= nums2[y]) {
                nums3[z] = nums1[x];
                x++;
            } else {
                nums3[z] = nums2[y];
                y++;
            }
            z++;
            s3++;
        }
        if(s3 < loc) {
            if(x >= nums1.length) {
                while(z < loc) {
                    nums3[z++] = nums2[y++];
                    s3++;
                }
            } else {
                while(z < loc) {
                    nums3[z++] = nums1[x++];
                    s3++;
                }
            }
        }
        if(length % 2 == 1) {
            return nums3[(length - 1) / 2];
        } else {
            return (double) (nums3[length / 2 - 1] + nums3[length / 2]) / 2;
        }
    }

    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int small = 0, big = 0;
        int length = nums1.length + nums2.length;
        int x = 0, y = 0, z = 0;
        while (x < nums1.length && y < nums2.length && z < length / 2 + 1) {
            if(nums1[x] <= nums2[y]) {
                small = big;
                big = nums1[x];
                x++;
            } else {
                small = big;
                big = nums2[y];
                y++;
            }
            z++;
        }
        if (x + y < length / 2 + 1) {
            if (x < nums1.length) {
                while (x < nums1.length && z < length / 2 + 1) {
                    small = big;
                    big = nums1[x];
                    x++;
                    z++;
                }
            } else {
                while (y < nums2.length && z < length / 2 + 1) {
                    small = big;
                    big = nums2[y];
                    y++;
                    z++;
                }
            }
        }
        if (length % 2 == 1) {
            return big;
        } else {
            return (double) (big + small) / 2;
        }
    }

    // 一种二分法思想，因为给定的数组已排好序
    // 中位数在第k个位置，则从两个数组分别找前 k / 2 - 1 个数，比较两数组第 k / 2 - 1个数的大小，小的则前 k / 2 - 1个数比不会是中位数
    // 这样就排除了 k / 2 - 1个数。在接下来的所有数中，中位数应该在 k - (k / 2 - 1)位置，按照刚才的逻辑继续
    // 时间复杂度为O(log(m + n))
    public double findMedianSortedArrays3(int[] nums1, int[] nums2) {
        return 0;
    }
}
